//
// Description: 440. 字典序的第K小数字
// Created by Loading on 2022/5/1.
//

#include <bits/stdc++.h>

using namespace std;

int findKthNumber(int n, int k) {
    /* 使用字典树的思想 */
    int current = 1;
    --k;
    // 得到当前节点下子节点的数目（包含当前节点）
    auto getSteps = [&]() {
        int steps = 0;
        /* 使用 long 防止计算越界 */
        long first = current;
        long last = current;
        while (first <= n) {
            // 使用 min(n, last)，防止多计算数量
            steps += (int) (min((long) n, last) - first + 1);
            first *= 10;
            last = last * 10 + 9;
        }

        return steps;
    };

    while (k) {
        int steps = getSteps();
        if (steps > k) {
            // 如果当前节点的子节点数目大于 k，说明第 k 个数在其子树中，继续向下一级寻找，去掉根节点
            current *= 10;
            --k;
        } else {
            // 如果当前节点的子节点数目小于等于 k，说明第 k 个数一定不在其子树中，向兄弟节点寻找，去掉 steps 个节点
            ++current;
            k -= steps;
        }
    }

    return current;
}

int main() {
    int n = 681692778;
    int k = 351251360;
    int res = findKthNumber(n, k);
    cout << res << endl;

    return 0;
}